/*
 * @lc app=leetcode.cn id=174 lang=java
 *
 * [174] 地下城游戏
 */

// @lc code=start
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] dp = new int[row][col];//dp[i][j]表示从(i,j)出发抵达终点所需的最少血量。
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=0;j--){
                if(i==row-1&&j==col-1){//最后一格，因为初始血量必须大于0，故最低取1。
                    dp[i][j] = Math.max(1,1-dungeon[i][j]);
                }else if(i==row-1){//已到达最后一行,这个状态可以由右边的状态转移过来。
                    dp[i][j] = Math.max(1, dp[i][j+1]-dungeon[i][j]);
                }else if(j==col-1){//同理，状态可由下面的状态转移过来
                    dp[i][j] = Math.max(1,dp[i+1][j]-dungeon[i][j]);
                }else{//普通情况，可选择从右转移，或从下转移，由于要最小血量，故要选最小dp值
                    dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}
// @lc code=end

